#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <utility>
using namespace std;

class bobject
{
public:
	virtual bool encode(byte*& dst) = 0;
	virtual bool decode(const byte*& src) = 0;

	static bool create_bobject(const char*& src, bobject*& obj)
	{
		if (src == NULL/* || obj == NULL*/)
			return false;
		switch (*src) {
		case 'i':
			obj = new binteger;
			break;
		case 'd':
			obj = new bdict;
			break;
		case 'l':
			obj = new blist;
			break;
		case '0'..'9':
			obj = new bstring;
			break;
		default:
			return false;
		}
		return true;//obj->decode(src);
	}

public:
	enum bobject_type {
		TYPE_STRING,
		TYPE_INTEGER,
		TYPE_LIST,
		TYPE_DICTIONARY,
	} type;
};

class bstring : public bobject
{
public:
	bstring() : type(TYPE_STRING){}
	bool encode(byte*& dst)
	{
		dst += sprintf(dst, "%d", str_.size());
		*dst++ = ':';
		memcpy(dst, str_.c_str(), str_.size());
		dst += str_.size();
	}

	bool decode(const char*& src)
	{
		if (src == NULL)
			return false;

		size_t len = 0;
		src += sscanf(src, "%ll", &len);
		if (*src != ':') return false;
		
		str_.resize(len);
		if (len > 0) {
			memcpy(&str_[0], src, len);
			src += len;
		}
		if (*src++ != 'e')
			return false;
		
		return true;
	}
public:
	string	str_;
};

class binteger : public bobject
{
public:
	binteger() : type(TYPE_INTEGER) {}
	binteger(int data) : type(TYPE_INTEGER), data_(data) {}
	bool encode(byte*& dst)
	{
		*dst++ = 'i';
		dst += sprintf(dst, "%d", data_);
		*dst++ = 'e';
	}

	bool decode(const byte * src)
	{
		if (NULL == src)
			return false;
		if (*src != 'i')
			return false;
		src += sscanf(src, "%ll", &data_);
		if (*src++ != 'e')
			return false;
		return true;
	}
public:
	long long	data_;
};

class blist : public bobject
{
public:
	blist() : type(TYPE_LIST){}
	bool encode(byte*& dst)
	{
		*dst++ = 'l';
		for (size_t i = 0; i < elems_.size(); ++i)
			elems_[i]->encode(dst);
		*dst++ = 'e';
	}

	bool decode(const byte * & src)
	{
		if (src == NULL)
			return false;
		if (*src++ != 'l')
			return false;
		bobject *obj;
		while (true) {
			if (!bobject::create_bobject(src, obj))
				return false;
			if (!obj->decode(src)) {
				delete obj;
				return false;
			}
 			elems_.push_back(obj);
			if (*src++ == 'e')
				break;
			src--;
		}
		return true;
	}
			

public:
	vector<bobject*>	elems_;
};

class bdict : public bobject
{
public:
	bdict() : type(TYPE_DICTIONARY){}
	bool encode(byte*& dst)
	{
		*dst++ = 'd';
		for (map<bstring, bobject>::const_iterator iter = elems_.begin();
			iter != elems_.end(); ++iter)
		{
			iter->first.encode(dst);
			iter->second.encode(dst);
		}
		*dst++ = 'e';
	}

	bool decode(const byte * & src)
	{
		if (src == NULL) return false;
		if (*src++ != 'd') return false;
		bobject *key = NULL, *value = NULL;
		while (true) {
			if (!bobject::create_bobject(src, key))
				return false;
			if (key->type != TYPE_STRING) {
				delete key;
				return false;
			}
			if (!key->decode(src)) {
				delete key
				return false;
			}
			bstring sKey = *key;
			delete key
			if (!bobject::create_bobject(src, value))
				return false;
			if (!value->decode(src)) {
				delete value;
				return false;
			}
			elems_[sKey] = value;
			if (*src++ == 'e')
				break;
			src--;
		}
		return true;
	}
public:
	map<bstring, bobject*> elems_;
};

